Loose Hamilton Cycles in Random Uniform Hypergraphs

Loose Hamilton Cycles in Random Uniform

Hypergraphs

Andrzej Dudek and Alan Frieze*

Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213

February 24, 2011

Abstract

In the random /c-uniform hypergraph H^^p-k of order n each possible /c-tuple
appears independently with probability p. A loose Hamilton cycle is a cycle of
order n in which every pair of adjacent edges intersects in a single vertex. We prove
that if pn^~^ / logn tends to infinity with n then

lim Pr{Hn^p-k contains a loose Hamilton cycle) = 1.

n— ^-oo

2{fc-l)|n

This is asymptotically best possible.

1 Introduction

The threshold for the existence of Hamilton cycles in the random graph Gn,p has been
known for many years, see, e.g., [1], |3] and [9]. There have been many generalizations of
these results over the years and the problem is well understood. It is natural to try to
extend these results to hypergraphs and this has proven to be difficult. The famous Posa
lemma fails to provide any comfort and we must seek new tools. In the graphical case,
Hamilton cycles and perfect matchings go together and our approach will be to build on
the deep and difficult result of Johansson, Kahn and Vu [8], as well as what we have
learned from the graphical case.

A k-uniform hypergraph is a pair {V,E) where E C In the random fc-uniform

hypergraph Hnp.^ of order n each possible fc-tuple appears independently with proba-
bility p. We say that a fc-uniform hj^ergraph (V, E) is a loose Hamilton cycle if there
exists a cyclic ordering of the vertices V such that every edge consists of k consecutive
vertices and every pair of consecutive edges intersects in a single vertex. In other words.

*Supported in part by NSF grant CCF0502793.

a loose Hamilton cycle has the minimum possible number of edges among all cycles on
\V\ vertices. In a recent paper the second author proved the following:

Theorem 1 (Frieze [1]) There exists an absolute constant K > such that if p >
K(\ogn)/n'^ then

\mi^Y*Y{Hn,p-z contains a loose Hamilton cycle) = 1.

4|?i

In this paper we refine the above theorem to A; > 4. Here we state our main result.
Theorem 2 Let k>3. If pn^~^ / \ogn tends to infinity together with n then

lim Pr {Hn,p;k contains a loose Hamilton cycle) = 1.

2{A:-l)|n

Thus {logn) /n^~^ is the asymptotic threshold for the existence of loose Hamilton
cycles, at least for n a multiple of 2(A; — 1). This is because if p < (1 — e)(A; — l)!(logn)/n^^^
and e > is constant, then whp0 Hn,p-k contains isolated vertices.

Notice that the necessary divisibility requirement for a fc-uniform hypergraph to have
a loose Hamilton cycle is {k — l)\n. In our approach we needed to assume more, namely,
2{k — l)\n (the same is true for Theorem [T]).

There are other ways of defining Hamilton cycles in hypergraphs, depending on the
size of the intersection of successive edges. As far as we know, when these intersections
have more than one vertex, nothing significant is known about existence thresholds.

Our proof uses a second moment calculation on a related problem. We cannot apply a
second moment calculation directly to the number of Hamilton cycles in Hn^p.^, this does
not work.

2 Proof of Theorem 2

Fix an integer k > 3. Set k = k — 2 and let n = 2(A; — l)m. We immediately see the
divisibility requirement 2{k — l)\n. Let pn^~^ / logn tend to infinity together with n (or
equivalently together with m). From on now, all asymptotic notations are with respect
to m.

We start with a special case of the theorem of [5]. Let S and T be disjoint sets. Let F =
T{S, T,p) be the random fc-uniform hypergraph such that each fc-edge in (2) ^ (^) is inde-
pendently included with probability p. Assuming that IS"! = 2m and \T\ = nm for some
positive integer m, a perfect matching of F is a set of m fc-edges {s2i-i, S2i,tj,i, . . .
1 < i < m, such that {si, . . . , S2m} = S and . . . , tm,K} = T.

Theorem 3 (Johansson, Kahn and Vu ^) There exists an absolute constant K > such
that if p > K{logn)/n'^~^ then whp F contains a perfect matching.

^An event occurs with, high probability, or whp for brevity, if lim„_i.oo Pr(£'„) = 1.

This version is not actually proved in [8], but can be obtained by straightforward
changes to their proof.

Now we (deterministically) partition [n] into X = [2m] and Y = [2m + l,n], where
clearly |X| = 2m and \Y\ = 2Km. We show that r{X,Y,p), which can be viewed as
the subgraph of Hn,p-k induced by {^) x (^), contains a loose Hamilton cycle whp.
Such a Hamilton cycle will consist of 2m edges of the form {xi, Xi^i, i/i^i, . . . , yi^n}^ where
1 < z < 2m, X2m+i =xi, {xi, . . . , X2m] = X and . . . , y2m,K] = Y-

Let d be an arbitrarily large even positive integer constant. Let X he a. set of size
2dm representing d copies of each x E X. Denote the jth copy of x G X by x^^^ E X and
let Xx = {x^^\ j = 1, 2, . . . , c?}. Then let Xi, X2, . . . , Xd be a uniform random partition
of X into d sets of size 2m. Define : X ^ X hy ipi{x^^^) = x for all j and x E X.
Similarly, we let 3^ be a set of size dum representing d/2 copies of each y E Y. Denote
the jth copy of y E Y by y^^) E y and let yy = {y^^\ j = 1,2,.. .,d/2}. Then let
Yi, Y2, . . . , Yd be a uniform random partition of y into d sets of size urn. Define 1^2 '■ y ^ Y
by My''^^) = y for all y E Y. Finally, let ip : Q x (^) ^ X^ x Y"" be such that

-^{j^l, J^2, 6, 6, • • • , ^k) = (^l(z^l), ^l(z^2), V^2(6), V^2(6), • • • , V^2(C«))-

Define pihy p = 1 — (1 — Pi)" where a = e^*"^. With this choice, we can generate Hn,p-k
as the union of a independent copies of Hn,p^-k- Similarly, define P2 by pi = 1 — (1 —p2Y-
Finally define p^ by p2 = 1 — (1— Pa)'^ where P = d'^{d/2)'^. Observe that piU^^^ / \ogn — )■ 00
for i = 1, 2, 3 as n — )• 00. In this way, Hn^p-j, is represented as the union of da/3 independent
copies of -ff„,p3;fc.

Now let an edge {ui, z/2, ^1, ^2, • • • , ^k} of r(Xj, Yj,p2), 1 < j < d,he spoiledif ipiii^i) =
or there exist 1 < r < s < k such that V'2(^r) = V^2(^s)- Let T{Xj,Yj,p2) be
obtained from T{Xj,Yj,p2) by removing all spoiled edges.

As we already mentioned Hn,p-k is represented as the union of da(3 independent copies
of Hn,p:i-k- We group the daf3 copies of Hn^p^^k together into a sets ^1, A2, ■ ■ ■ , Aa in such
a way that each collection Ai, 1 < « < a, consists of d sub-collections Bij, 1 < j < d,
where Bij comprises (3 independent copies of if„,p3;fc- Let Aij denote the union of these
/3 copies in Bij and let Sj denote the union of Aij over all 1 < j < c?. Basically Ajj and
Sj can be viewed as copies of -ffn,p2;fc and Hn^p-^-k, respectively.

Now for fixed 1 < i < a and I < j < d, we couple an independent copy of f (Xj, Yj,p2)
with a sub-hypergraph (induced by {^) x (^)) of the union of /3 independent copies of
Hn,p3;k in Bij as follows. First we enumerate these (3 copies of Hn^p^-k as Hj^^,,,j^, where
1 < ji, J2 < d and 1 < J3, • • • dk < d/2. Next we place {xi < X2,yi < y2 < ■ ■ ■ < yn] in
-^iivjfc; whenever there exist ji, . . . ,jk such that {xi^\x2^\yi^\ . . . , y^''^} is an edge in
t{Xj,Y^,P2).

Fix 1 < i < a for the moment and consider Aj j for all 1 < j < d. Let Mj, 1 < j < d,
be a perfect matching of r{Xj,Yj,p2) as promised by Theorem [31 At this point what
we can say is that Xi, X2, . . . , Xd is a uniform random partition of X and Yi,Y2, . . . ,Yd
is a uniform random partition of 3^. Furthermore, if Mj exists then by symmetry we
can assume that it is a uniformly random matching of r{Xj,Yj,p2). What we want
though are unspoiled matchings. Fortunately, it is reasonably likely that Mj contains no

spoiled edges. Our argument will be (see Lemma [5] below) that there is a probability
of at least e~'^'^ that Mj C r[Xj,Yj,p2) simultaneously for all 1 < j < d. That means
that with the same probability ip{Mj) C Aij simultaneously for all 1 < j < d, i.e.,
ip{Mi U M2 U ■ ■ ■ U Md) C Ej. It follows that then with probability at least

l-((l-o(l))(l-e-'^'^)r>l-e-^'' (1)

there is an i such that Sj contains a copy of the following hypergraph = tp{Mi U M2 U
■ ■ ■ U Md), where each Mj is a random perfect matching of t'iXj, Yj,pi), i.e., Mj has no
spoiled edges. (The first 1 — o(l) factor in ([T]) comes from the use of Theorem [3]). We will
choose such an i for constructing A^. These matchings are still independently chosen, once
we have fixed the partitions Xi, X2, . . ■ , Xd and Yi, ^2, • • • , and each Mj is uniformly
random from f (X^, Yj^pi) by symmetry. On the other hand, the partitions of A", y are no
longer uniform. Their probability of selection depends on how many unspoiled matchings
they contain.

Our main auxiliary result, see Theorem |6l shows that the hypergraph A^ contains a
loose Hamilton cycle with probability at least 1— Sk/c?. Because we have pn^~^ / log n 00
we can make d arbitrarily large and consequently this and ([1]) imply that

lim Pr{Hn,p-k has no Hamilton cycle) < lim ( H — — ] =0.

n— >-oo ' ' d— j-oo V d J

This completes the proof of Theorem [2l

Remark 4 It is important to understand the distribution of A^. It is the union of match-
ings Ml, M2, . . . , Md obtained by repeating the following experiment until the occurrence
of W:

(i) choose uniform random partitions of X, y; and then

(ii) choose uniform random matchings Mj of r(Xj, Yj,p2).

Lemma shows that we should not have to wait too long until U occurs. We do not
choose one set of partitions and then choose the matchings conditional on U.

3 Auxiliary results

We will use a configuration model type of construction to analyze A^ (see, e.g., [2| or
Section 9.1 in [B]). X is represented as 2dm points partitioned into 2m cells Xx,x G X of
d points. Analogously y is represented as dum points partitioned into 2Km cells yy, y eY
of d/2 points. To construct A^ we take a random pairing of X into dm sets Ci, 62, ... , edm
of size two and a random partition /i, /2, • • • , fdm of y into dm sets of size k. The edges
of Kd will be il^leiU fi) for £ = 1, 2, ... , md. We condition on U.

We will now argue that this model is justified. First of all ignore the event U. To
generate Mi, M2, . . . , M^, we can take a random permutation tti of X and a random

permutation 112 of y. We let Xj = {7ri(2(j — l)m + i), i = 1, . . . , 2m} and then Mj^x will
consist of ei = {vri(2£ — 1), 7ri(2£)} for £ = (j — l)m + 1, . . . , jm. We construct the fi
and Y^- and M^ y in a similar way from 112. So 7ri,7r2 generate the same hypergraph when
viewed either as originally described in terms of Mi, M2, . . . , Ma or as described in terms
of a configuration model. Each sequence Mi, M2, . . . , M^ is equally likely in both models.
The relationship between models will therefore continue to hold even if we condition on
the event U.

As already noted in Remark |U is the above model conditioned on the event U. We
generate a conditioned sample by repeatedly generating Mi, M2, . . . , M^ until the event
U occurs. In our analysis of the configuration model we deal with U directly. We use a
second moment method and compute our moments conditional on U.

3.1 Spoiled edges

Suppose that for every 1 < j < d there exists a perfect matching Mj of r(Xj, Yj,p2). We
show that it is reasonably likely that Mi U • ■ ■ U M^ contains no spoiled edges.
Let U be the event:

{Mj C t{Xj, Yj,p2),foT each j = 1,2, . . . ,d} = {MiU- ■ -UM^ contains no spoiled edges}.
Lemma 5 Suppose that k > 1 and d is a positive even integer. Then, H

Pr(W I Mj exists for each j = 1, 2, . . . , d) ~ exp |-^^^ - i^^i^llKlzL^ | > g-'^'^.

Proof. Our model for Mj will be a collection of sets {xj^2£-i,Xj^2£, Zj/}, where Mj^x =

Xj^2} , • • • , {xj,2m-iXj,2m} is a raudom pairing of Xj and Mj^y = ^j,2, • • • , ^i,m
is a random partition of Yj into sets of size k. We can obtain all of the {xj^2e-i,Xj^2e},
for all j and i, by taking a random permutation of X and then considering it in dm
consecutive sub-sequences Ii,l2, ■ ■ ■ , I dm of length 2. Let Si denote the number of pairs
^1,1^2 of elements in X with = V'i(^2) that appear in some Ii. Similarly, we can

obtain all of the the Zj^e by taking a random permutation of y and then considering it in
dm consecutive sub-sequences Ji, J2, ■ ■ ■ , Jdm of length k. Let now S2 denote the number
of pairs ^1, ,^2 of elements in 3^ with ip2{^i) = i^2{(,2) that appear in some Jg. Then for any
constant t > 1, we obtain

E(M..-i)...(..-..i))-^<r)(2*^)*-(^)'

and

^We write Am ^ B„i to signify that Am = (1 + o{l))B„i as, m ^ 00.

It follows that Si and 5*2 are asymptotically Poisson with means and
respectively. Now Si and S2 are independent and so + ^2 is asymptotically Poisson
with mean + ^^d

Pr(Mj C T{Xj, Yj,p2), for each j = 1,2, . . . , d \ Mj exists for each j = 1,2, . . . ,d)

= Pr(S'i + 5*2 = I Mj exists for each j = 1,2, . . . ,d)

r d-l U-l)(d-2)

~ exp <

^ \ 2 4

> e-"^

as required. □

3.2 Loose Hamilton cycles in random bipartite hypergraphs

Recall that A* is a set of size 2dm representing d copies of each x G X and 3^ is a set
of size dnm representing d/2 copies of each y E Y, where |X| = 2m and \Y\ = 2nm.
Let Xi,X2, . . . ,Xct be a uniform random partition of X into d sets of size 2m and let
Yi,Y2, . . . ,Yct be a uniform random partition of y into d sets of size nm. For every
1 ^ J < c^; let Mj be a random matching of ("^^) x (^^) conditioned on lA i.e. without
spoiled edges. That means Mj is a set of m disjoint /c-edges in ("^^) x (^^) such that no edge
contains two representatives of the same element oi X UY . Let = ip{Mi U ■ ■ ■ U M^).

Theorem 6 Suppose that k > 1 and d is a sufficiently large positive even integer. Then,

d 3k

Pr(Arf contains a loose Hamilton cycle) > 2 — (1 + o(l))\l — > 1 -.

a — 2[k + 1) d

A similar result for k = 1 was already established by Janson and Wormald [7] using a
different terminology.

Let if be a random variable which counts the number of loose Hamilton cycles in
Ad such that the edges only intersect in X. Note that every such loose Hamilton cycle
induces an ordinary Hamilton cycle of length 2m in X and a partition of Y into K-sets.

Lemma 7 Suppose that n>l and d is a positive even integer. Then,
Hence, limm->oo E(//) = 00 for every d > e'^^^ + 1.

The last conclusion holds since for d > e'*"'"^ + 1,

> (<;-l)exp{--^^(d-2;

= {d - 1) exp{-{K + 1)}

> 1.

Lemma 8 Suppose that n > 1 and d is a sufficiently large positive even integer. Then,

^'*^'< (1 + 0(1)).' "

Now Theorem IH] easily follows from this, since

3.2.1 Expectation (the proof of Lemma [7])

Let a 2m-cycle in A* be a set of 2m disjoint pairs of points of X such that they form a
2m-cycle in X (i.e. a Hamilton cycle) when they are projected by ipi to X. Let p2m be
the probability that a given set of 2m disjoint pairs of points of X forming a 2m-cycle is
contained in a random configuration and that U holds.

First note that from the proof of Lemma [5] the number of configurations partioned
into 2m cells of d points for which U holds is asymptotically

~ e-('^-^)/2(2rfm - 1)!! = ^-(^-1)72 i^dm)\

^ ' 2'^™(c/m)! ^ '

After fixing the pairs in a 2m-cycle we have to randomly pair up lid — 2)m points. In
other words, we want to compute the number of configurations partioned into 2m cells of
[d — 2) points for which U. holds. Hence, again by Lemma we get,

_g-(d-3)/2(2(d-2)m-l)!!

and

g~(<i-3)/2/2M _ 2)m - 1)!! {2dm - 4m - 1)!!

e

e-(''-i)/2(2rfm- 1)!! (2dm-\)\\ '

Next, let be the number of possible 2m-cycles on X . From (9.2) in [6] we get,

l))2™(2m)!

'mi

Let q2m be the probabihty that a randomly chosen set U of 2nm points of y (represented
by 2m K-sets) is equal (after the projection '1IJ2) to F, i.e., 4'2{U) = Y. Note that U must

Consequently,

E{H) = a2mP2mq2m

{«+i)/2^^''^^^^™(^ - l)2™(2m)!(2c/m - 4m - l)!!(2/tm)!(/trfm - 2Km)\
^ ^ 22'^™+2m(2rfm - l)!!(Kc/m)! '

Using the Stirling formula yields Lemma El Recall that (2iV - 1)!! ~ y/2 (^)^.
3.2.2 Variance (the proof of Lemma [8j)

Let Ci and C2 be two 2m-cycles in X sharing precisely b pairs. Clearly, IC1UC2I = Am — b.
Denote by P2m{b) the probability that Ci and C2 are contained in a random configuration
of X for which U holds. (Clearly, p2m(2m) = P2m)- First note that if we ignore U then
the number of configurations containing Ci and C2 equals

Next conditioning on U we obtain that the number of configurations containing Ci and
C2 is bounded from above by

Let U and W be two randomly chosen collections of 2m K-sets in y satisfying \W\ =
\U\ = 2m and |iy \ f/| = 2m — b. Let r2mip) be the probability that both U and W are
both equal (after the projection ■?/)2) to F, i.e., ip2{U) = ip2iW) = Y. Conditioning on
'ip2{U) = Y we have {d/2 — i^^^m-Kb ^Kdm-2Kmj choices for W. Thus, similarly as

in ([3]) we obtain

{2dm-2{4m-b) - 1)!!

g-(d-5)/2^2rfm - 2(4m - 6) - 1)!!
(The factor e~^'^~^-*'^^ corresponds to the case when b = 0.) Hence,

2 (2dm -8m + 26- 1)!!
' {2dm - 1)!!

(3)

Moreover, let N{b) be the number of 2m-cycles in X that intersect a given 2m-cycle in b
pairs. By [B] (cf. last equation on page 253), we get

N{b)= ^ n - 2)^"+"-^(^ - 3)^'"-°-^(2m -b-l)\(^) (^"^

a=0

where for a = 6 = we set f = 1.

b

Consequently,
E(i72) 1 N{b)p2Ub)r2rrXb)

a

<

E{Hy - E{H) ' ^ a^mPlmQl

2m— 1 min{6,2m— 6}

X (rf-3)

2m— a— 6

6\ /2m - 6\ (2m - b)\{2dm - 8m + 26 - l)!!(2rfm - 1)!!

X

a/ V a J (2m)!(2c?m - 4m - 1)!!^

2 Km

Below we ignore all cases for which a = 0,a = 6ora + 6 = 2m since their contribution
is negligible as can be easily checked by the reader. Using the Stirling formula, the terms
in the sum can be written as

^ h{a/{2m),b/{2m))exp{2m- g{a/{2m),b/{2m))}

X (^1 +

where

min{a, b — a, 2m — a — 6} + 1

g{x, y) = x log(2) - log(d) - \og{d - I) + {I + x - y) \og{d - 2)

+ {l-x-y) log(rf - 3) + y log(y) + 2(1 - y) log(l - y)

— {y — x) log(y — x) — 2x log(x) — {1 — X — y) log(l — x — y)

+ {d/2 -2 + y) log(rf - 4 + 2?/) + (rf/2) log(rf) - (rf - 2) log(rf - 2)

+ K{d/2 - 1) log(rf) + k{1 - y) log(l -y) + K{d/2 -2 + y) \og{d -A + 2y)

-K{d-?> + y) \og{d - 2)

and

■^(d-2)iy(l-y)(l-x-y)(y-x)

Although the next computations may be verified by hand, the reader might find the assis-
tance of Mathematica useful. We give the definitions of g{x, y) and /i(x, y) in Mathematica
format in Appendix \M

Now we analyze function g{x, y) in the domain

S = {{x,y) : < X < y < 1 — x}.

First, we compute the first derivatives:
dq

^ = log(2) - log((i - 3) + log((i - 2) - 2 log(x) + log(-x + y) + log(l - x - y)

1^ = - \og{d -3)-{1 + k) \og{d -2)-{2 + k) log(l - y)
dy

+ log(l -x-y) + \og{y) - \og{-x + y) + (1 + /«) log(ci - 4 + 2y).

Let (a;o,|/o) = (2(ci - 2)/{d{d - l)),2/d). Note that since g(a;o,2/o) = |(a;o,2/o) = 0,
i^Q-i Uo) is a critical point of g and g{xo, yo) — 0. Let D^g be the Hessian matrix of second
derivatives. Routine calculations show that

2 + ^1 1 _J_ + L

^ y) — I 1 , 1 2+K , _1_ I 1 I 1 I 2(1+k)

x+y -l+x+y l-y x-y ~^ y ~^ -1+x+y ~^ -4+d+2y

Hence,

(d-lfd (d-4)(d-l)^d

D g{xo,yo) -
One can verify that

Det{D''g{xo,yo)) =

2(d-3) 2((i-2)((i-3)
(d-4)(d-iyd d(16+d(-34+d(28+(-9+d)d-2K)+6K)
2(d-2)(d-3) 2(d-3)(d-2)2

4(ci-3)(ci-2)2

Since — ^2(^-3)^ < ^'^'^ Det(D^5((a;o, |/o)) > for > 2(1+k), we conclude that D'^g{xo, yo)
is negative definite at {xo,yo). Hence, g has a local maximum there. Now we show that
(xo,l/o) is the unique global maximum point of g in S. Moreover, we argue that that
g{x,y) has no asymptote near the boundary of S, nor does it approach a limit which is
greater than (for d large enough) .
First recall that the function

/^M^) ifO<z<l,
^ ^ \0 if z = Oor z = l ^ ^

is continuous on [0,1]. Consequently, function g{x,y) can be extended to a continuous
function on

T = {{x,y) : < X < y < 1 — x}.

Note that -l/e< f{z) <0 (cf. @). Thus,

g{x, y) < log(2) - log(rf) - \og{d ~l) + {l + x-y) \og{d - 2)
+ {l-x-y) \og{d - 2) + +
+ l/e + 2/e + l/e

+ (rf/2 -2 + y) \og{d - 2) + (rf/2) log(rf) - (rf - 2) \og{d - 2)
+ K(d/2 - 1) log(d) + + ft(ci/2 -2 + y) \og{d - 2)
- - 3 + \og{d - 2)
= -l/log(t/-2) + o(log(rf)),

where the last term o{\og{d)) does not depend on x and y. Hence, there is a large enough
d such that g{x, y) < for all points in the domain {{x,y) G T : 1/2(3 + 2k) < ?/}.

Denote by dT the boundary of T, i.e., = T \ S. In order to finish, it is enough to
show that:

(i) the only critical point in {{x,y) G T \ dT : y < 1/2(3 + 2k)} is {xo,yo), and

(ii) ^(x,y) < for all points in {{x,y) E dT : y < 1/2(3 + 2k)}.

Solving the equation ^{x,y) = for x, noting that the equation is linear in x, we
obtain

_ y{l - y) {{d -3){d- 2)^+\l - y)^+^ -{d-4 + 2y)'^+^)
^ ~ (1 - y)^+^{d -3){d- 2)^^+1 -y{d-4: + 2y)^+^ '

Substituting this expression for x in ||(x,?/) = (actually in exp{^{x,y)} = 1) yields
the equation

= ij{y) = 2(l-2y)2(l-y)-(d-4 + 22/)'^+i(rf-2)''+2_^(l_^)2-+2(g_5^ + ^2)2^^_2)2«
+ 2y{l - y)''+\d - 4 + 2y)'+^{d - 3)(rf - 2)"+^ - ?/(rf - 4 + 2y)^+^\

We see from our previous considerations that ipiyo) = 0. It remains to show that for
large d, yo is the only value in {y : < y < 1/2(3 + 2k)} for which ip{y) = 0. To this
end we show that ip'{y) < implying that ip{y) is a monotone function (and clearly also
continuous). From the definition of ipiv) "we get,

^'(y) = [-y{l - y)2-+2(6 - 5d + d^f{d - 2)2-)' + 0(c/2-+3)

= (1 - y)^''^\-l + y{2K + 3))^^''+^ + 0{d^''^''),

where the hidden constant in 0{d'^'^^^) does not depend on y. Hence, for a sufficiently
large d the derivative il)'{y) < for all < y < 1/2(3 + 2k) (independently from d). This
shows that holds.

We split dn]) into three cases. One is for = x < y, one for < x = y and the last one
for X = y = Q. Note that

9i{y) = 9(0, y)

= - log(rf) - log(d - 1) + (1 - log(rf - 2)

+ (1 - log(t/ - 3) + 2(1 - y) log(l - - (1 - log(l - y)
+ {d/2 -2 + y) \og{d -4 + 2y) + {d/2) log(d) - (d - 2) \og{d - 2)
+ K{d/2 - 1) log(d) + k{1 - y) log(l - + K(ci/2 -2 + y) log{d -4 + 2?/)
3 + y) log(rf-2).

Recall that < y < 1/2(3 + 2k). It is easy to check that

g[{y) = -\og{d) + o{\og{d)),

where the last term o{\og{d)) does not dependent on y.

Thus, for d sufficiently large gi (y) is a decreasing function. Hence, by continuity

gi{y)<giiO) = 9(0,0).

Later we show that g{0, 0) < 0.

Now let < X = ?/ < 1/2(3 + 2k). Define

92{y) = 9{y,y)

= y log(2) - log(d) - log(d - 1) + log(d - 2)

+ (1 - 2y) \ogid -3)+y log(y) + 2(1-1/) log(l - y)
-2ylog{y)-il-2y) \og{l - 2y)

+ {d/2 -2 + y) log(rf -4: + 2y) + {d/2) \og{d) - {d - 2) log{d - 2)

+ K{d/2 - 1) \og{d) + k{1 - y) log(l -y) + K{d/2 -2 + y) \og{d - 4 + 2y)

-K{d-3 + y) log{d-2).

Consequently,

g'M = log(2) - 2 log(d -3)-K \og{d - 2) + 2 log(l - 2y)

-{2 + k) log(l -y)- \og{y) + {1 + k) \og{d -4 + 2y)

and

g'^{y) = {2 + k)/{1 - y) - 1/y + 4/(-l + 2y) + 2(1 + K)/{d -A + 2y).

Note that since < y < 1/2(3 + 2k) we get that for d large enough (72(2/) < 0. Thus,
(72(1/) is a decreasing function. Moreover, since

y-S>0+

and

^^(2/d)=21og((rf-4)/(rf-3))<0,

we conclude that (72 (y) has a local maximum at ^ G (0, 2/c/]. Clearly such local maximum
is the global maximum in the interval (0,1/2(3 + 2k)]. Unfortunately, it is not clear
how to determine ^ since the equation g2{y) = seems not to have any "nice" solution.
Therefore, we define a new auxiliary function

gsiy) = 92{y) - {2/3){d/2)Hog{{d - 4)/{d - 3))^^

on {0,2/d\. Clearly (72(1/) < Qziy)- Thus in order to show that (72(0 < ^1 suffices to
prove that g^iii) < for any y G (0,2/c?]. Analogously to analyzing (72(1/) one can show
that (73(1/) < for (i large enough. Moreover, since g'^{2/d) = 0, we get that g^^y) is an
increasing function on {0,2/ d]. Thus,

gsiy) < gz{2/d) = (8/3d - 1) \og{{d - A)/{d - 3)) + log((rf - 2)/{d - 1)). (5)

As one can check the right hand side in ^ is negative for sufficiently large d, as required.
It remains to show that (7(0, 0) < 0. By continuity we get

(7(0,0)= \im g2{y)<g-i{2/d)<Q.

This completes the proof of dH]) and so the proof of showing that (xq, yo) is the unique
global maximum in T.

The rest of argument is totally standard for such variance calculations (see, e.g., [3 [6]).
Finally, we obtain

r2^

^<(1

o(l))^y" j /i(xo, 2/0) exp I -i(zi,Z2)D^5'(xo, 2/0) (^1,^2)^1 c^^i c?^2

Det(D2^(xo,yo))^/'

{d-l)d^ 2{d-2)y/d^

2{d-2)y/d^ {d - 1) d%d - 2{1 + k))
d

-2(k + 1)'

as required.

4 Concluding remarks

In this paper, we showed that (logn)/?T,'^~^ is the asymptotic threshold for the existence
of loose Hamilton cycles in Hn^p-k for n a multiple of 2{k — 1). It would be nice to drop
this divisibility requirement and replace it by the necessary {k — l)\n, as mentioned in
Introduction. We address this question in our future work.

5 Acknowledgment

We would like to thank the anonymous referee for carefully reading this manuscript, many
helpful comments and pointing out some errors in the previous version of this manuscript.
We are also very grateful to Svante Janson and Nick Wormald for fruitful discussions about
contiguity of random regular graphs (contiguity was used in the previous version of this
paper) .

References

[1] M. Ajtai, J. Komlos and E. Szemeredi, The first occurrence of Hamilton cycles in
random graphs, Annals of Discrete Mathematics 27 (1985), 173-178.

[2] B. BoUobas, A probabilistic proof of an asymptotic formula for the number of labelled
regular graphs, European Journal of Combinatorics 1 (1980), 311-316.

[3] B. Bollobas, The evolution of sparse graphs, in Graph Theory and Combinatorics,
Academic Press, Proceedings of Cambridge Combinatorics, Conference in Honour of
Paul Erdos (B. Bollobas; Ed) (1984), 35-57.

[4] A.M. Frieze, Loose Hamilton cycles in random 3-uniform hypergraphs. Electronic Jour-
nal of Combinatorics 17 (2010), N28.

[5] A.M. Frieze, M. Jerrum, M. MoUoy, R. Robinson and N. Wormald, Generating and
counting Hamilton cycles in random regular graphs. Journal of Algorithms 21 (1996),
176-198.

[6] S. Janson, T. Luczak and A. Rucihski, Random Graphs, Wiley, 2000.

[7] S. Janson and N. Wormald, Rainbow Hamilton cycles in random regular graphs. Ran-
dom Structures Algorithms 30 (2007), 35-49.

[8] A. Johansson, J. Kahn and V. Vu, Factors in random graphs. Random Structures and
Algorithms 33 (2008), 1-28.

[9] J. Komlos and E. Szemeredi, Limit distributions for the existence of Hamilton circuits
in a random graph. Discrete Mathematics 43 (1983), 55-63.

A Mathematica expressions

For convenience, we replace here nhy k.

g[x_,y_,d_,k_] = X Log[2] - Log[d] - Log[d - 1] + (1 + x - y) Log[d - 2] \
+ (1 - X - y) Log[d - 3] + y Log[y] + 2 (1 - y) Log[l - y] \

- (y - x) Log[y - x] - 2 x Log[x] - (1 - x - y) Log[l - x - y] \

+ (d/2 - 2 + y) Log[d - 4 + 2 y] + (d/2) Log[d] - (d - 2) Log[d - 2] \

+ k(d/2 - 1) Log[d] + k(l - y) Log[l - y] + k(d/2 - 2 + y) Log[d - 4 + 2 y] \

- k(d - 3 + y) Log[d - 2] ;

li[x_,y_,d_] = Sqrt[d(-4 + d + 2 y)] / Sqrt[(d-2)-2 y(l-y) (1 - x - y)(y-x)];